package leetcode.offer_two_special.array;

import java.util.HashMap;

/**
 * 双指针和滑动窗口使用的一个必要条件就是能一步一步迭代，确定窗口的收缩方向，
 * 这有负数，就完全不知道是左边缩小，还是右边缩小了
 *
 * @author mazouri
 * @create 2021-09-05 9:41
 */
public class _10_subarraySum {
//    public int subarraySum(int[] nums, int k) {
//        int sum = 0;
//        int count = 0;
//        int left = 0;
//
//        for (int right = 0; right < nums.length; right++) {
//            sum += nums[right];
//
//            while (left <= right && sum >= k) {
//                if (sum == k) {
//                    count++;
//                }
//                sum -= nums[left++];
//
//            }
//        }
//        return count;
//    }

    public int subarraySumForce(int[] nums, int k) {
        int count = 0;
        for (int begin = 0; begin < nums.length; begin++) {
            int sum = 0;
            for (int end = begin; end < nums.length; end++) {
                sum += nums[end];
                if (sum == k) count++;
            }
        }
        return count;
    }

    public int subarraySum(int[] nums, int k) {
        int preSum = 0;
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int num : nums) {
            preSum += num;
            if (map.containsKey(preSum - k)) {
                count += map.get(preSum - k);
            }
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }


    public static void main(String[] args) {
        System.out.println(new _10_subarraySum().subarraySum(new int[]{3,4,7,2,-3,1,4,2,1}, 7));
    }
}
